package node;

import element.BasicElement;
import java.util.ArrayList;
import structure.Identifiable;

/**
 *
 * @author Vojta
 */
public class BinaryNode extends Node {

    protected BinaryNode parent;
    protected BinaryNode leftChild;
    protected BinaryNode rightChild;

    public BinaryNode(int id) {
        element = new BasicElement(id);
    }

    /**
     * Metoda prida potomka do spravneho podstromu. Pokud je pridavany uzel vetsi nez aktualni uzel,
     * prida se do praveho podstromu, pokud mensi, prida se do leveho.
     * @param n Pridavany uzel
     * @return True, pokud se pridani povede. False, pokud uzel se stejnym klicem se jiz ve stromu 
     * nachazi.
     */
    public boolean addChild(BinaryNode n) {
        if (equals(n)) {
            return false;
        }
        if (compareTo(n) == 1) {
            return addChildLeft(n);
        } else {
            return addChildRight(n);
        }
    }

    protected boolean addChildLeft(BinaryNode n) {
        if (leftChild == null) {
            setLeftChild(n);
            n.setParent(this);
            return true;
        } else {
            return leftChild.addChild(n);
        }
    }

    protected boolean addChildRight(BinaryNode n) {
        if (rightChild == null) {
            setRightChild(n);
            n.setParent(this);
            return true;
        } else {
            return rightChild.addChild(n);
        }
    }

    /**
     * Metoda odstrani uzel, na kterem je zavolana. Kazde odstraneni uzlu prevede na
     * odstraneni listu. Rozlisuje se odstraneni uzlu s levym, pravym a zadnym podstromem.
     * @return True, pokud je odstranen posledni uzel (v BinaryTree je potom potreba
     * nastavit root na null).
     */
    public boolean remove() {
        if (leftChild != null) {
            return replaceWithMaxFromLeft();
        }
        if (rightChild != null) {
            return replaceWithMinFromRight();
        }
        return removeAsLeaf();
    }

    /**
     * Metoda prohodi obsah uzlu, na kterem je zavolana, s obsahem uzlu, ktery je maximem
     * v levem podstromu. Tim zustava zachovana vlastnost BVS.
     * @return 
     */
    protected boolean replaceWithMaxFromLeft() {
        BinaryNode max = leftChild.findMax();
        //switchElements(max);
        switchParents(max);
        switchChilds(max);
        return remove();
    }

    /**
     * Metoda prohodi obsah uzlu, na kterem je zavolana, s obsahem uzlu, ktery je minimem
     * v pravem podstromu. Tim zustava zachovana vlastnost BVS.
     * @return 
     */
    protected boolean replaceWithMinFromRight() {
        BinaryNode min = rightChild.findMin();
        //switchElements(min);
        switchParents(min);
        switchChilds(min);
        return remove();
    }

    /**
     * Metoda odstrani uzel jako list (je potreba zajistit, aby to list byl).
     * Ukoncuje rekurzi odstranovani uzlu.
     * @return 
     */
    protected boolean removeAsLeaf() {
        switch (getNodePosition()) {
            case ROOT:
                return true;
            case LEFT_SUBTREE:
                parent.setLeftChild(null);
                return false;
            case RIGHT_SUBTREE:
                parent.setRightChild(null);
                return false;
            default:
                return false;
        }
    }

    protected void switchParents(BinaryNode n) {
        NodePosition position = getNodePosition();
        NodePosition nPosition = n.getNodePosition();
        BinaryNode temp = parent;
        setParent(n.parent);
        n.setParent(temp);

        switch (position) {
            case ROOT:
                break;
            case LEFT_SUBTREE:
                if (temp != null) {
                    temp.setLeftChild(n);
                }
                break;
            case RIGHT_SUBTREE:
                if (temp != null) {
                    temp.setRightChild(n);
                }
                break;
        }

        switch (nPosition) {
            case ROOT:
                break;
            case LEFT_SUBTREE:
                if (parent != null) {
                    parent.setLeftChild(this);
                }
                break;
            case RIGHT_SUBTREE:
                if (parent != null) {
                    parent.setRightChild(this);
                }
                break;
        }
    }

    protected void switchChilds(BinaryNode n) {
        switchLeftChilds(n);
        switchRightChilds(n);
    }

    protected void switchLeftChilds(BinaryNode n) {
        if (leftChild != null && n.leftChild != null) {
            leftChild.switchParents(n.leftChild);
        } else if (leftChild != null) {
            n.setLeftChild(leftChild);
            leftChild.setParent(n);
            setLeftChild(null);
        } else if (n.leftChild != null) {
            setLeftChild(n.leftChild);
            leftChild.setParent(this);
            n.setLeftChild(null);
        }
    }

    protected void switchRightChilds(BinaryNode n) {
        if (rightChild != null && n.rightChild != null) {
            rightChild.switchParents(n.rightChild);
        } else if (rightChild != null) {
            n.setRightChild(rightChild);
            rightChild.setParent(n);
            setRightChild(null);
        } else if (n.rightChild != null) {
            setRightChild(n.rightChild);
            rightChild.setParent(this);
            n.setRightChild(null);
        }
    }

    /**
     * Vyhleda uzel s danym klicem.
     * @param id Klic.
     * @return Hledany uzel nebo null.
     */
    public BinaryNode find(int id) {
        if (id == getId()) {
            return this;
        }
        if (id < getId()) {
            if (leftChild != null) {
                return leftChild.find(id);
            } else {
                return null;
            }
        } else {
            if (rightChild != null) {
                return rightChild.find(id);
            } else {
                return null;
            }
        }
    }

    /**
     * Metoda spocita pocet uzlu v podtromu aktualniho uzlu.
     * @return Pocet uzlu v podstromu.
     */
    public int countDescedant() {
        int left = (leftChild != null) ? leftChild.countDescedant() : 0;
        int right = (rightChild != null) ? rightChild.countDescedant() : 0;
        return left + right + 1;
    }

    /**
     * Metoda spocita hloubku podstromu aktualniho uzlu.
     * @return Hloubka podstromu.
     */
    public int subtreeHeight() {
        int left = (leftChild != null) ? leftChild.subtreeHeight() : 0;
        int right = (rightChild != null) ? rightChild.subtreeHeight() : 0;
        return Math.max(left, right) + 1;
    }

    /**
     * Metoda najde maximum v podstromu.
     * @return Maximum.
     */
    public BinaryNode findMax() {
        if (rightChild == null) {
            return this;
        } else {
            return rightChild.findMax();
        }
    }

    /**
     * Metoda najde minimum v podstromu.
     * @return Minimum.
     */
    public BinaryNode findMin() {
        if (leftChild == null) {
            return this;
        } else {
            return leftChild.findMin();
        }
    }

    public void sort(ArrayList<Identifiable> l) {
        if (leftChild != null) {
            leftChild.sort(l);
        }
        l.add(element);
        if (rightChild != null) {
            rightChild.sort(l);
        }
    }

    /**
     * Metoda zkouma, zda uzel lezi v levem, nebo pravem podstromu z hlediska sveho predka.
     * @return ROOT, pokud uzel rodice nema, LEFT_SUBTREE, pokud lezi v pravem podstromu,
     * RIGHT_SUBTREE, pokud lezi v levem podstromu.
     */
    protected NodePosition getNodePosition() {
        if (parent == null) {
            return NodePosition.ROOT;
        } else {
            if (parent.getLeftChild() != null && parent.getLeftChild().equals(this)) {
                return NodePosition.LEFT_SUBTREE;
            } else {
                return NodePosition.RIGHT_SUBTREE;
            }
        }
    }

    public BinaryNode getParent() {
        return parent;
    }

    public void setParent(BinaryNode parent) {
        this.parent = parent;
    }

    public BinaryNode getLeftChild() {
        return leftChild;
    }

    public void setLeftChild(BinaryNode leftChild) {
        this.leftChild = leftChild;
    }

    public BinaryNode getRightChild() {
        return rightChild;
    }

    public void setRightChild(BinaryNode rightChild) {
        this.rightChild = rightChild;
    }

    public String toString(int tab) {
        StringBuilder sb = new StringBuilder();
        if (getLeftChild() != null) {
            sb = sb.append(leftChild.toString(tab + 1));
            sb = sb.append("\n\r");
        }
        for (int i = 0; i < tab; i++) {
            sb = sb.append("\t");
        }
        sb = sb.append(toString());
        if (getRightChild() != null) {
            sb = sb.append("\n\r");
            sb = sb.append(rightChild.toString(tab + 1));
        }
        return sb.toString();
    }
}
